package wh.实现strStr函数;

public class Str {

    public static void main(String[] args) {
        int str = str("", "");
        System.out.println("输出");
        System.out.println(str);
    }

//调用string类的api解法
    public static int str(String haystack,String needle){
        int length2 = needle.length();
        if(needle.equals("")){
            return 0;
        }
        char c = needle.charAt(0);
        int index = haystack.indexOf(c,0);
        while (index <= haystack.length()) {
            if (index == -1 || haystack.length() < needle.length() || haystack.length() - index < needle.length()) {
                return -1;
            } else if (c == ' ') {
                return 0;
            }
            String substring = haystack.substring(index, index + length2);
            if (substring.equals(needle)) {
                //System.out.println(index);
                return index;
            }else {
                int index2 = haystack.indexOf(c, index + 1);
                index = index2;
            }
        }
        return 0;
    }


    //数组解法
    public static int str2(String ss,String pp){
        int n = ss.length();
        int m = pp.length();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        //0是发起点，n - m是结束点
        for (int i = 0; i < n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i,b = 0;
            while (b < m && s[a] == p[b]){
                a++;
                b++;
            }
            //如果能够完全匹配，返回原串的「发起点」下标
            if (b == m)
                return i;
        }
        return -1;
    }

        // KMP 算法
        // ss: 原串(string)  pp: 匹配串(pattern)
        public static int strStr(String ss, String pp) {
            if (pp.isEmpty()) return 0;

            // 分别读取原串和匹配串的长度
            int n = ss.length(), m = pp.length();
            // 原串和匹配串前面都加空格，使其下标从 1 开始
            ss = " " + ss;
            pp = " " + pp;

            char[] s = ss.toCharArray();
            char[] p = pp.toCharArray();

            // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
            int[] next = new int[m + 1];
            // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
            for (int i = 2, j = 0; i <= m; i++) {
                // 匹配不成功的话，j = next(j)
                while (j > 0 && p[i] != p[j + 1]) j = next[j];
                // 匹配成功的话，先让 j++
                if (p[i] == p[j + 1]) j++;
                // 更新 next[i]，结束本次循环，i++
                next[i] = j;
            }

            // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
            for (int i = 1, j = 0; i <= n; i++) {
                // 匹配不成功 j = next(j)
                while (j > 0 && s[i] != p[j + 1]) j = next[j];
                // 匹配成功的话，先让 j++，结束本次循环后 i++
                if (s[i] == p[j + 1]) j++;
                // 整一段匹配成功，直接返回下标
                if (j == m) return i - m;
            }

            return -1;
        }
}
